package com.wfb.sort;

/**
 * 七种排序 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 堆排序
 *
 * @author 18118
 *
 */
public class Sort {
    /**
     * 交换两个数在数组中的位置
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int arr[], int i, int j) {
        int num = arr[i];
        arr[i] = arr[j];
        arr[j] = num;
    }

    public static void main(String[] args) {
        // 测试数据
        int[] arr = { 6, 9, 2, 7, 1, 3, 8, 4, 0, 8,8,3,34,34,453,66,342,54362,43,77,5,44,54,34,343,3};
        // 冒泡排序
//		maoPaoSort(arr);
        // 选择排序
//		selectSort(arr);
        // 插入排序
//		insertSort(arr);
        // 希尔排序
//		xiErSort(arr);
        // 快速排序
//		quickSort(arr, 0, arr.length - 1);
        // 归并排序
//		guiBingSort(arr, 0, arr.length - 1);
        // 堆排序
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 创建堆，
     *
     */
    public static void heapSort(int[] arr) {
        // 创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            // 从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        // 调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            // 将堆顶元素与末尾元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆
     *
     */
    public static void adjustHeap(int[] arr, int parent, int length) {
        // 将temp作为父节点
        int temp = arr[parent];
        // 左孩子
        int lChild = 2 * parent + 1;
        while (lChild < length) {
            // 右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[lChild]) {
                break;
            }
            // 把孩子结点的值赋给父结点
            arr[parent] = arr[lChild];
            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }

    /**
     * 归并排序 ：将数组拆开在拆开然后使他们分别有序，然后合并 分解
     */
    public static void guiBingSort(int[] arr, int left, int right) {
        if (left >= right) {// 递归出口，左侧下表大于等于右侧代表已经分完
            return;
        }
        int m = (left + right) / 2;// 每次递归进行二分
        guiBingSort(arr, left, m);// 对二分后的左侧再次二分
        guiBingSort(arr, m + 1, right);// 对二分后的右侧再次二分
        merge(arr, left, m, right);// 对分好的数组进行合并
    }

    /**
     * 归并
     */
    public static void merge(int[] arr, int left, int m, int right) {
        // 拆分后的数组下标
        int s1 = left;
        int s2 = m + 1;
        // 临时数组
        int a[] = new int[right - left + 1];
        // 临时数组a[]的下标
        int i = 0;
        // 循环判断两边的每一个元素谁小把谁拉下来
        while (s1 <= m && s2 <= right) {
            if (arr[s1] <= arr[s2]) {
                a[i] = arr[s1];
                i++;
                s1++;
            } else {
                a[i] = arr[s2];
                i++;
                s2++;
            }
        }
        // 下边两个循环只有一个可以执行，因为合并到最后至多只有一个数组未合并完成
        // 未合并的数据代表是最大的数据，直接拉下来就是有序的
        while (s1 <= m) {
            a[i] = arr[s1];
            i++;
            s1++;
        }
        while (s2 <= right) {
            a[i] = arr[s2];
            i++;
            s2++;
        }
        // 最后将临时数组中的数据拷贝到主数组中
        for (int j = 0; j < a.length; j++) {
            // j为临时数组的下标
            // 主数组需要拷贝的位置为当前段左侧下标依次加上临时数组下标
            arr[j + left] = a[j];
        }

    }

    /**
     * 快速排序 每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆， 然后递归执行该过程，直到所有元素都完成排序。
     *
     * @param arr
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            // 递归出口条件左右两个指针走到同一个位置
            return;
        }
        int i = left - 1;// 当前逻辑分组左侧指针
        int j = right + 1;// 当前逻辑分组右侧指针
        int num = arr[(left + right) / 2];// 任意取出一个基准
        while (i < j) {
            do {
                i++;
            } while (num > arr[i]);// 若左边元素更小无需交换i向后移
            do {
                j--;
            } while (num < arr[j]);// 若右边元素大则无需交换j向前移动
            if (i < j) {// 此时左右两个指针还未重合符合算法要求
                // 交换位置
                swap(arr, i, j);
            }
        }
        // 对基准值两侧进行递归操作
        quickSort(arr, left, j);// 对左侧逻辑分组执行以上重复操作
        quickSort(arr, j + 1, right);// 对右侧进行以上重复操作
    }

    /**
     * 希尔排序 将数据进行分组，对每组进行插入排序，然后逐渐减小分组间隔重复以上步骤直到分组间隔为1 分组间隔通常使用长度的一半
     *
     * @param arr
     */
    public static void xiErSort(int[] arr) {
        int pace = arr.length;// 记录一下总长度
        while (pace > 1) {
            pace /= 2;// 每次分组进行折半
            for (int i = pace; i < arr.length; i += pace) {// 若pace=3则这组数据为arr[3],arr[6],arr[9]
                for (int j = i - pace; j >= 0; j--) {// 对这组数据进行插入排序
                    if (arr[j + pace] < arr[j]) {// 举个例子若arr[6]>arr[3]则进行交换
                        swap(arr, j + 1, j);
                    }
                }
            }

        }
    }

    /**
     * 插入排序 将初始数据分为有序部分和无序部分， 每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        // 刚开始有序部分长度为1，经过比较有序部分逐渐增长
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                // 将无序序列中的一个数跟有序序列从后往前比较弱前一个数大于后一个数则交换位置，
                // 由此逐渐将前半段化为有序
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j + 1, j);
                }
            }
        }
    }

    /**
     * 冒泡排序 相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。 整个过程如同气泡冒起，因此被称作冒泡排序。
     *
     * @param arr
     */
    public static void maoPaoSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {// 外层循环控制需要比较的趟数
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }

    }

    /**
     * 选择排序 选出所有数据中最小的一个放在序列前面，接下来从剩余序列重复以上操作，知道剩余序列长度为0
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;// 记录最小值下标默认使用第一个
            for (int j = i + 1; j < arr.length; j++) {// i+1个开始比较
                if (arr[j] < arr[minIndex]) {// 对比两个位置
                    // 如果后者比已知的最小值更小则更新所记录的最小值位置
                    minIndex = j;
                }
            }
            // 一轮循环后将找到的最小值放到剩余数据最前面
            swap(arr, i, minIndex);
        }

    }

}
